package lpg;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;

class Pda
{
    //
    // Constructor
    //
    Pda(Control control)
    {
        this.control    = control;
        this.option     = control.option;
        this.grammar    = control.grammar;
        this.base       = control.base;
        this.dfa        = control.dfa;
        this.produce    = control.produce;
    }

    //
    // Given an item of the form: [x .A y], where x and y are arbitrary strings,
    // and A is a non-terminal, we pretrace the path(s) in the automaton  that
    // will be followed in computing the look-ahead set for that item in
    // stateNo.  A number is assigned to all pairs (S, B), where S is a state,
    // and B is a non-terminal, involved in the paths. gotoIndex points to the
    // GOTO_ELEMENT of (stateNo, A).
    //
    private void traceLalrPath(int stateNo, int gotoIndex)
    {
        //
        //  If STATE is a state number we first check to see if its base
        // look-ahead set is a special one that does not contain EMPTY and
        // has already been assigned a slot that can be reused.
        // ((laBase[STATE] != OMEGA) signals this condition.)
        // NOTE that look-ahead follow sets are shared only when the maximum
        // look-ahead level allowed is 1 and single productions will not be
        // removed. If either (or both) of these conditions is true, we need
        // to have a unique slot assigned to each pair [S, A] (where S is a
        // state, and A is a non-terminal) in the automaton.
        //
        Dfa.GotoTriplet goTo = dfa.statset.element(stateNo).goTo.get(gotoIndex);
        int state = goTo.action();
        if (state > 0 && (laBase[state] != Util.OMEGA &&
                          option.lalrLevel == 1 &&
                          !option.singleProductions &&
                          !option.backtrack))
        {
            goTo.setLaptr(laBase[state]);
            return;
        }

        //
        // At this point, R points to a list of items which are the successors
        // of the items needed to initialize the Look-ahead follow sets.  If
        // anyone of these items contains EMPTY, we trace the Digraph for other
        // look-ahead follow sets that may be needed, and signal this fact
        // using the variable containsEmpty.
        //
        laTop++;   // allocate new slot
        goTo.setLaptr(laTop);
        boolean containsEmpty = false;
        IntArrayList stateList = new IntArrayList();
        Node kernelRoot = (state > 0 ? dfa.statset.element(state).kernelItems : base.adequateItem[-state]);
        for (Node r = kernelRoot; r != null;  r = r.next)
        {
            int item = r.value - 1;
            if (base.first(base.itemTable[item].suffixIndex).get(grammar.empty))
            {
                containsEmpty = true;
                int lhsSymbol = grammar.rules.get(base.itemTable[item].ruleNumber).lhs;
                dfa.access(stateList, stateNo, item);
                for (int k = 0, m = stateList.size(); k < m; k++)
                {
                    int accessState = stateList.get(k);
                    Dfa.GotoHeader goToHeader = dfa.statset.element(accessState).goTo;
                    int i = goToHeader.index(lhsSymbol);
                    if (goToHeader.get(i).laptr() == Util.OMEGA)
                        traceLalrPath(accessState, i);
                }
            }
        }

        //
        // If the look-ahead follow set involved does not contain EMPTY, we
        // mark the state involved (STATE) so that other look-ahead follow
        // sets which may need this set may reuse the same one.
        // NOTE that if containsEmpty is false, then STATE has to denote a
        // state number (positive value) and not a rule number (negative).
        //
        if (!containsEmpty)
            laBase[state] = goTo.laptr();
    }

    //
    // COMPUTE_READ computes the number of intermediate look-ahead sets that
    // will be needed (in laTop), allocates space for the sets(laSet), and
    // initializes them.
    // By intermediate look-ahead set, we mean the set of terminals that may
    // follow a non-terminal in a given state.
    // These sets are initialized to the set of terminals that can immediately
    // follow the non-terminal in the state to which it can shift (READ set).
    //
    private void computeRead()
    {
        if (option.lalrLevel > 1 || option.singleProductions || option.backtrack)
        {
            readSet = new BitSet[dfa.numStates + 1];
            for (int i = 1; i <= dfa.numStates; i++)
                readSet[i] = new BitSet(grammar.numTerminals + 1);
        }

        //
        //  We traverse all the states and for all complete items that requires
        // a look-ahead set, we retrace the state digraph (with the help of the
        // routine TRACE_LALR_PATH) and assign a unique number to all look-ahead
        // follow sets that it needs. A look-ahead follow set is a set of
        // terminal symbols associated with a pair [S, A], where S is a state,
        // and A is a non-terminal:
        //
        // [S, A] --> Follow-set
        // Follow-set = {t | t is a terminal that can be shifted on after
        //                      execution of a goto action on A in state S}.
        //
        // Each follow set is initialized with the set of terminals that can be
        // shifted on in state S2, where GOTO(S, A) = S2. After initialization
        // a follow set F that does not contain the special terminal symbol
        // EMPTY is marked with the help of the array laBase, and if the
        // highest level of look-ahead allowed is 1, then only one such set is
        // allocated, and shared for all pairs (S, B) whose follow set is F.
        //
        IntArrayList stateList = new IntArrayList();
        laBase = new int[dfa.numStates + 1];
        Arrays.fill(laBase, Util.OMEGA);
        int laTop = 0;
        for (int stateNo = 1; stateNo <= dfa.numStates; stateNo++)
        {
            for (Node p = ((option.lalrLevel <= 1 && singleCompleteItem[stateNo])
                            ? null
                            : dfa.statset.element(stateNo).completeItems);
                 p != null;
                 p = p.next)
            {
                int itemNo = p.value;
                int ruleNo = base.itemTable[itemNo].ruleNumber;
                int lhsSymbol = grammar.rules.get(ruleNo).lhs;
                if (lhsSymbol != grammar.acceptImage)
                {
                    dfa.access(stateList, stateNo, itemNo);
                    for (int k = 0, m = stateList.size(); k < m; k++)
                    {
                        int accessState = stateList.get(k);
                        Dfa.GotoHeader goTo = dfa.statset.element(accessState).goTo;
                        int i = goTo.index(lhsSymbol);
                        if (goTo.get(i).laptr() == Util.OMEGA)
                            traceLalrPath(accessState, i);
                    }
                }
            }

            //
            //  If the look-ahead level is greater than 1 or single productions
            // actions are to be removed when possible or we need to trace backtrack
            // information, then we have to compute
            // a Follow-set for all pairs [S, A] in the state automaton. Therefore,
            // we also have to consider Shift-reduce actions as reductions, and
            // trace back to their roots as well.
            // Note that this is not necessary for Goto-reduce actions. Since
            // they terminate with a non-terminal. Each such terminating non-terminal
            // is followed by the empty string and it must produce a
            // rule that either ends up in a reduction, a shift-reduce, or another
            // goto-reduce. It will therefore be taken care of automatically by
            // transitive closure.
            //
            if (option.lalrLevel > 1 || option.singleProductions || option.backtrack)
            {
                Dfa.ShiftHeader sh = dfa.shift(stateNo);
                for (int j = 0, n = sh.size(); j < n; j++)
                {
                    if (sh.get(j).action() < 0)
                    {
                        int ruleNo = -sh.get(j).action();
                        int lhsSymbol = grammar.rules.get(ruleNo).lhs;
                        int itemNo = base.adequateItem[ruleNo].value - 1;
                        dfa.access(stateList, stateNo, itemNo);
                        for (int k = 0, m = stateList.size(); k < m; k++)
                        {
                            int accessState = stateList.get(k);
                            Dfa.GotoHeader goTo = dfa.statset.element(accessState).goTo;
                            int i = goTo.index(lhsSymbol);
                            if (goTo.get(i).laptr() == Util.OMEGA)
                                traceLalrPath(accessState, i);
                        }
                    }
                }

                //
                // When more than one lookahead is requested, we also need
                // to compute the set of terminal symbols that can be read
                // in a state entered via a terminal transition.
                //
                if (option.lalrLevel > 1 && stateNo != 1)
                {
                    Node q = dfa.statset.element(stateNo).kernelItems;
                    int itemNo = q.value - 1;
                    if (grammar.isTerminal(base.itemTable[itemNo].symbol))
                    {
                        readSet[stateNo] = base.first(base.itemTable[itemNo].suffixIndex);
                        for (q = q.next; q != null; q = q.next)
                        {
                            itemNo = q.value - 1;
                            readSet[stateNo].or(base.first(base.itemTable[itemNo].suffixIndex));
                        }
                    }
                }
            }
        }


        //
        //   We now allocate space for laIndex and laSet, and initialize
        // all its elements as indicated in reduce.h. The array laBase is
        // used to keep track of Follow sets that have been initialized. If
        // another set needs to be initialized with a value that has been
        // already computed, laBase is used to retrieve the value.
        //
        Arrays.fill(laBase, Util.OMEGA);
        laIndex = new int[laTop + 1];
        laSet = new BitSet[laTop + 1];
        for (int i = 0; i <= laTop; i++)
            laSet[i] = new BitSet(grammar.numTerminals + 1);

        for (int stateNo = 1; stateNo <= dfa.numStates; stateNo++)
        {
            Dfa.GotoHeader goTo = dfa.statset.element(stateNo).goTo;
            for (int i = 0, n = goTo.size(); i < n; i++)
            {
                int laPtr = goTo.get(i).laptr();
                if (laPtr != Util.OMEGA)   // Follow Look-ahead needed
                {
                    int state = goTo.get(i).action();
                    Node q;
                    if (state > 0)
                    {
                        if (laBase[state] != Util.OMEGA)  // already computed
                        {
                            laIndex[laPtr] = laIndex[laBase[state]];
                            laSet[laPtr] = laSet[laBase[state]];
                            q = null;
                        }
                        else
                        {
                            laBase[state] = laPtr;
                            q = dfa.statset.element(state).kernelItems;
                        }
                    }
                    else
                        q = base.adequateItem[-state];

                    if (q != null)
                    {
                        int itemNo = q.value - 1; // initialize with first item
                        laSet[laPtr] = base.first(base.itemTable[itemNo].suffixIndex);
                        for (q = q.next; q != null; q = q.next)
                        {
                            itemNo = q.value - 1;
                            laSet[laPtr].or(base.first(base.itemTable[itemNo].suffixIndex));
                        }
                        laIndex[laPtr] = (laSet[laPtr].get(grammar.empty) ? Util.OMEGA : Util.INFINITY);
                        if (option.lalrLevel > 1 || option.singleProductions || option.backtrack)
                        {
                            if (state > 0)
                                readSet[state] = (BitSet)laSet[laPtr].clone();
                        }
                    }
                }
            }
        }
    }

    //
    // LA_TRAVERSE takes two major arguments: stateNo, and an index (gotoIndex)
    // that points to the GOTO_ELEMENT array in stateNo for the non-terminal
    // left hand side of an item for which look-ahead is to be computed. The
    // look-ahead of an item of the form [x. A y] in state stateNo is the set
    // of terminals that can appear immediately after A in the context summarized
    // by stateNo. When a look-ahead set is computed, the result is placed in
    // an allocation of LA_ELEMENT pointed to by the laPtr field of the
    // GOTO_ELEMENT array.
    //
    // The same digraph algorithm used in MKFIRST is used for this computation.
    //
    void laTraverse(int stateNo, int gotoIndex)
    {
        Dfa.GotoHeader goTo = dfa.statset.element(stateNo).goTo;
        int laPtr = goTo.get(gotoIndex).laptr();
        stack.add(laPtr);
        int index = stack.size();
        laIndex[laPtr] = index;

        //
        // Compute STATE, action to perform on Goto symbol in question. If
        // STATE is positive, it denotes a state to which to shift. If it is
        // negative, it is a rule on which to perform a Goto-Reduce.
        //
        IntArrayList stateList = new IntArrayList();
        int state = goTo.get(gotoIndex).action();
        for (Node r = (state > 0 ? dfa.statset.element(state).kernelItems : base.adequateItem[-state]);
             r != null;
             r = r.next)
        {  // loop over items [A.x lhsSymbol . y]
            int item = r.value - 1;
            if (base.first(base.itemTable[item].suffixIndex).get(grammar.empty))
            {
                int symbol = grammar.rules.get(base.itemTable[item].ruleNumber).lhs;
                dfa.access(stateList, stateNo, item); // states where RULE was introduced through closure
                for (int k = 0, m = stateList.size(); k < m; k++)
                {
                    //
                    // Search for GOTO action in access-state after reducing
                    // RULE to its left hand side (SYMBOL). Q points to the
                    // GOTO_ELEMENT in question.
                    //
                    int accessState = stateList.get(k);
                    goTo = dfa.statset.element(accessState).goTo;
                    int i = goTo.index(symbol);
                    int gotoLaptr = goTo.get(i).laptr();
                    if (laIndex[gotoLaptr] == Util.OMEGA)
                        laTraverse(accessState, i);
                    laSet[laPtr].or(laSet[gotoLaptr]);
                    laIndex[laPtr] = Math.min(laIndex[laPtr], laIndex[gotoLaptr]);
                }
            }
        }

        if (laIndex[laPtr] == index) // Top of a SCC
        {
            int top = stack.size() - 1;
            for (int i = stack.remove(top); i != laPtr; i = stack.remove(--top))
            {
                laSet[i] = (BitSet)laSet[laPtr].clone();
                laIndex[i] = Util.INFINITY;
            }
            laIndex[laPtr] = Util.INFINITY;
        }
    }

    //
    // COMPUTE_LA takes as argument a state number (stateNo), an item number
    // (itemNo), and a set (lookAhead).  It computes the look-ahead set of
    // terminals for the given item in the given state and places the answer in
    // the set lookAhead.
    //
    private void computeLa(int stateNo, int itemNo, BitSet lookAhead)
    {
        stack.clear(); // empty the stack
        int lhsSymbol = grammar.rules.get(base.itemTable[itemNo].ruleNumber).lhs;
        if (lhsSymbol == grammar.acceptImage && base.itemTable[itemNo].symbol == grammar.empty)
        {
            lookAhead = base.first(base.itemTable[itemNo - 1].suffixIndex);
            return;
        }
    
        lookAhead.clear();
        if (grammar.isTerminal(base.itemTable[itemNo].symbol)) // note that the symbol may be "empty"
        {
            lookAhead.set(base.itemTable[itemNo].symbol);
        }
        else
        {
            lookAhead = base.nonterminalFirst(base.itemTable[itemNo].symbol);
            if (lookAhead.get(grammar.empty))
            {
                lookAhead.clear(grammar.empty);
                lookAhead.or(base.first(base.itemTable[itemNo].suffixIndex));
            }
        }
    
        if (lookAhead.get(grammar.empty))
        {
            IntArrayList stateList = new IntArrayList();
            dfa.access(stateList, stateNo, itemNo);
            for (int k = 0, m = stateList.size(); k < m; k++)
            {
                //
                // If look-ahead after left hand side is not yet computed,
                // LA_TRAVERSE the graph to compute it.
                //
                int accessState = stateList.get(k);
                Dfa.GotoHeader goTo = dfa.statset.element(accessState).goTo;
                int i = goTo.index(lhsSymbol);
                if (laIndex[goTo.get(i).laptr()] == Util.OMEGA)
                    laTraverse(accessState, i);
                lookAhead.or(laSet[goTo.get(i).laptr()]);
            }
            lookAhead.clear(grammar.empty); // empty not valid look-ahead
        }
    }

    void processPDA()
    {
    }

    void processPDAOutput()
    {
    }

    void printShiftState(int i)
    {
    }

    private int maximumSymbolNameLength(int a)
    {
        return -1;
    }

    private void printShifts(Dfa.ShiftHeader a, int b)
    {
    }

    private void printGotos(Dfa.GotoHeader a, int b)
    {
    }

    private void printReductions(Dfa.ReduceHeader a, int b)
    {
    }

    private void printLaState(int a)
    {
    }

    private void processConflictActions()
    {
    }

    //
    // Add SYMBOL to the set of symbols CONFLICT_SYMBOLS[stateNo].
    //
    private void addConflictSymbol(int stateNo, int symbol)
    {
        conflictSymbols.get(stateNo).add(symbol);
    }

    boolean notLrk = false;

    int maxLaState = 0;
    int highestLevel = 0;
    int numReductions = 0;
    int numShiftReduceConflicts = 0;
    int numReduceReduceConflicts = 0;
    int numShiftShiftConflicts = 0;
    int numSoftShiftReduceConflicts = 0;
    int numSoftReduceReduceConflicts = 0;

    private final Control control;
    private final Option option;
    private final Grammar grammar;
    private final Base base;
    private final Dfa dfa;
    private final Produce produce;

    //
    // STACK is used in la_traverse to construct a stack of symbols.
    // The boolean vector singleCompleteItem identifies states whose
    // kernel consists of a single final item and other conditions allows
    // us to compute default reductions for such states.
    // The vector laBase is used in COMPUTE_READ and TRACE_LALR_PATH to
    // identify states whose read sets can be completely computed from
    // their kernel items.
    //
    private final IntArrayList stack = new IntArrayList();
    private boolean[] singleCompleteItem = null;
    private int[] laBase = null;
    private int laTop = 0;

    //
    // CONFLICT_SYMBOLS is a mapping from each state into a set of terminal
    // symbols on which an LALR(1) conflict was detected in the state in
    // question.
    //
    private final List<IntArrayList> conflictSymbols = new ArrayList<IntArrayList>(4096);

    //
    // laIndex and laSet are temporary look-ahead sets, each of which will
    // be pointed to by a GOTO action, and the associated set will be
    // initialized to readSet(S), where S is the state identified by the GOTO
    // action in question. readSet(S) is a set of terminals on which an action
    // is defined in state S. See COMPUTE_READ for more details.
    // laTop is used to compute the number of such sets needed.
    //
    // The boolean variable NOT_LRK is used to mark whether or not a grammar
    // is not LR(k) for any k. NOT_LRK is marked true when either:
    //    1. The grammar contains a nonterminal A such that A =>+rm A
    //    2. The automaton contains a cycle with each of its edges labeled
    //       with a nullable nonterminal.
    // (Note that these are not the only conditions under which a grammar is
    //  not LR(k). In fact, it is an undecidable problem.)
    // The variable HIGHEST_LEVEL is used to indicate the highest number of
    // lookahead that was necessary to resolve all conflicts for a given
    // grammar. If we can detect that the grammar is not LALR(k), we set
    // HIGHEST_LEVEL to INFINITY.
    //
    private BitSet[] readSet = null;
    private BitSet[] laSet = null;
    private int[] laIndex = null;

}
